package sort;

public class HeapSort { // 堆排序  时间复杂度O(N * logN)
    public static void main(String[] args) {
        int[] arr = new int[]{65,9,23,18,43,5,36};
        HeapSort.createMaxHeap(arr);
        System.out.println();
    }
    public static void heapSort(int[] array){
        createMaxHeap(array);
        int end = array.length - 1;
        while (end > 0){
            Swap.swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }
    public static void createMaxHeap(int[] array){
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0 ; parent--) {
            shiftDown(array, parent, array.length);

        }
    }
    public static void shiftDown(int[] array, int parent, int end){
        int child = 2 * parent + 1;
        while (child < end){
            if(child < end - 1 && array[child] < array[child + 1]){
                child++;
            }
            if(array[child] > array[parent]){
                int temp = array[child];
                array[child] = array[parent];
                array[parent] = temp;
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }
}
